Grafos
Um grafo é um par ordenado (V,A) , onde V é o conjunto de vértices e A é o conjunto de arestas. Podemos representar os vértices usando pontos e as arestas utilizando segmentos de retas ou arcos ligando os pontos. Dá para pensar nos vértices como objetos e nas arestas com a relação entre eles. O número de vértices é denotado por |V| (em alguns lugares ele é denotado por N ou n ). Já o número de arestas será denotado por A (em alguns lugares ele é denotado por E ou m ). Para dizermos que o conjunto dos vértices é referente a um grafo G , podemos escrever V(G) . Da mesma forma, neste caso, poderemos denotar o conjunto das arestas por A(G) . Definição Quando dois vértices estão ligados por uma ou mais arestas, dizemos que eles são adjacentes (ou vizinhos). O conjunto dos vértices adjacentes a v é denotado por N(v) . Definição Quando uma aresta está ligada a um vértice, dizemos que ela é incidente a ele. Definição Dois vértices podem ser ligados por mais de uma aresta. Neste caso, diremos que elas são arestas múltiplas. Definição Uma aresta pode ligar um vértice a si mesmo. Neste caso, a aresta é chamada de laço. Definição Um grafo que não possui arestas múltiplas e nem laços é chamado de grafo simples. Existem livros que tratam como grafos apenas os grafos simples e chamam os grafos que não são simples de multigrafos. Definição O número de arestas que incidem sobre um vértice v é chamado de grau. Denotaremos o grau de v por d(v) . Teorema Zero dos Grafos A soma dos graus dos vértices de um grafo é igual ao dobro do número de arestas. Em outras palavras, {\displaystyle \sum _{v \in G}d(v)}=2|A|. Você pode aprender um pouco mais sobre somatórios aqui. Lema do Aperto de Mão O número de vértices de grau ímpar de um grafo é par. Caminho Um caminho é uma sequência de arestas, cada uma das quais começando no ponto final da anterior. Ciclos Um caminho fechado é chamado de ciclo. Um ciclo de k vértices também é chamado de ' k -ciclo' e denotado por C_k . Exemplo (Cone Sul 2013) Semciclolândia é um país com 500 cidades e 2013 estradas de mão dupla, cada uma conectando diretamente duas cidades. Duas cidades A e B são chamadas de vizinhas se existe uma estrada que as conecta e duas cidades A e B são chamadas de quase-vizinhas se existe uma cidade C tal que A é vizinha de C e C é vizinha de B . Sabemos que em Semciclolândia não existem duas cidades conectadas diretamente por mais de uma estrada e não existem quatro cidades A,B,C e D tais que simultaneamente A é vizinha de B , B é vizinha de C , C é vizinha de D e D é vizinha de A . Demonstrar que existe uma cidade que é quase-vizinha de pelo menos 57 cidades. Solução: Vamos usar um grafo G de 500 vértices e 2013 arestas para representar o problema. Seja d_2(v) o número de quase-vizinhos de v . A afirmação: "não existem quatro cidades A,B,C e D tais que simultaneamente A é vizinha de B , B é vizinha de C , C é vizinha de D e D é vizinha de A " é equivalente a dizer que não existem 4 -ciclos no grafo. Se A e B são quase-vizinhos, então só existe um vértice adjacente a ambos. De fato, se existissem dois, digamos C e D , então haveria um 4 -ciclo, o que contradiz o enunciado. Como saber a quantidade de quase-vizinhos de v ? Considere w um vértice vizinho de v . Todos os vértices vizinhos de w (com exceção de v ) são quase-vizinhos de v . Ou seja, existirão d(w)-1 quase-vizinhos de v que são adjacentes a w . Para descobrirmos a quantidade de quase vizinhos de v , basta somarmos os vizinhos dos vizinhos de v que não são v . Em outras palavras, devemos somar d(w)-1 para cada vizinho w de v . Assim d_2(v)={\displaystyle \sum _{w \in N(v)}d(w)-1}. Com isso, {\displaystyle \sum _{v \in G}d_2(v)}={\displaystyle \sum _{v \in G}{\displaystyle \sum _{w \in N(v)}d(w)-1}}. Vamos entender melhor este somatório. Para cada vértice w , quantas vezes d(w)-1 aparecerá na conta? Aparecerá uma vez para cada vértice que w estiver conectado, ou seja, ela aparecerá d(w) vezes. Com isso, a soma poderá ser escrita como {\displaystyle \sum _{v \in G}d_2(v)}={\displaystyle \sum _{w \in G}d(w)(d(w)-1)}={\displaystyle \sum _{w \in G}d(w)^2-d(w)}={\displaystyle \sum _{w \in G}d(w)^2}-{\displaystyle \sum _{w \in G}d(w)}= =\left({\displaystyle \sum _{w \in G}d(w)^2}\right)-2|A|.(*) O que fazer com isto? Sabemos mexer com {\displaystyle \sum _{w \in G}d(w)} por causa do Teorema Zero dos Grafos. Mas e quanto a {\displaystyle \sum _{w \in G}d(w)^2} ? Observe que isto é quase uma média quadrática. Se usarmos a Desigualdade das Médias que envolve as médias quadráticas e lembrarmos que existem 500 vértices no grafo, \sqrt{\frac {500}} \geq \frac {500}. Pelo Teorema Zero dos Grafos, \sqrt{\frac {500}} \geq \frac{2|A|}{500} \Leftrightarrow {\displaystyle \sum _{w \in G}d(w)^2} \geq \frac{|A|^2}{125}. Se voltarmos a (*) , {\displaystyle \sum _{v \in G}d_2(v)}=\left({\displaystyle \sum _{w \in G}d(w)^2}\right)-2|A| \geq \frac{|A|^2}{125}-2|A|=\frac{2013^2}{125}-2\cdot 2013.(**) Porém se tivermos d_2(v) \leq 56 para todo vértice v , como existem 50 vértices, segue que {\displaystyle \sum _{v \in G}d_2(v)} \leq 56 \cdot 50 = 2800. O que contradiz (**) . Logo, deve existir algum vértice v tal que d(v) \geq 57 . Grafos Conexos Dizemos que um grafo é conexo se para quaisquer dois pontos existe um caminho que os liga. Caso isto não aconteça, o grafo será chamado de desconexo. Neste caso, ele terá várias partes conexas. Cada uma delas será chamada de componente conexa. Árvores Grafos conexos que não possuem ciclos são chamados de árvores. O vértice de grau 1 de uma árvore é chamado de folha (ou raiz). Toda árvore com dois ou mais vértices possui pelo menos duas folhas. Já se um grafo não for conexo e não tiver ciclos, ele será chamado de floresta. Grafos Isomofos Dois grafos são isomorfos se representam a mesma situação. Grafos Eulerianos Um grafo conexo é chamado de euleriano se for possível encontrar um caminho passando por todas as arestas exatamente uma vez. Teorema Um grafo é euleriano se, e somente se, possui nenhum ou exatamente dois vértices de grau ímpar. Outros Lugares Para Estudar * Você pode praticar grafos eulerianos com este aplicativo chamado One Line. Bibliografia * FOLMIN, Dmitri; GENKIN, Sergey; ITENBERG, Ilia. Círculos Matemáticos - A Experiência Russa. Rio de Janeiro: IMPA, 2012. * WILSON, Robin J. Introduction to Graph Theory. l.: Academic Press, 1972. * ZEITZ, Paul. The Art and Craft of Problem Solving. l.: Wiley, 2006. Categoria:Matemática Categoria:Combinatória